#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
//课时16
/*读取10个整型数据12 63 58 95 41 35 65  0 38 44，
然后通过冒泡排序，快速排序，插入排序，分别对该组数据进行排序，输出3次有序结果，每个数的输出占3个空格*/

typedef int ElemType;
typedef struct
{
    ElemType *data;
    int size;
}Stable;

void init_stable1(Stable &st,int length)
{
    st.size=length;
    st.data=(ElemType*)malloc(sizeof(ElemType)*length);
    int num;
    for(int i=0; i<length; i++)
    {
        scanf("%d",&num);
        st.data[i]=num;
    }
}

void init_stable2(Stable &st,int length)
{
    st.size=length;
    st.data=(ElemType*)malloc(sizeof(ElemType)*length);
}

//打印数组
void print_stable(Stable st)
{
    for(int i=0; i< st.size ; i++)
    {
        printf("%3d",st.data[i]);
    }
    printf("\n");
}

//插入排序
void insert_sort(int* a,int len)
{
    int i,j;
    for(i=1; i<len; i++)
    {
        int insertVal=a[i];
        for(j=i-1; j>=0 && insertVal < a[j]; j--)
        {
            a[j+1]=a[j];
        }
        a[j+1]=insertVal;
    }

}

//快速排序（挖坑法）
void quick_sort(int *data,int left,int right)
{
    if(left >= right)  //递归结束条件
        return;
    int key=data[left];  //确定基准值
    int head=left,tail=right;  //head往后移动找大，tail往后移动赵小
    while(head < tail)
    {
        while(head < tail && data[tail] >= key) //找到小于key值时停下
        {
            --tail;
        }
        data[head]=data[tail];
        while(head < tail && data[head] <= key) //找到大于key值时停下
        {
            head++;
        }
        data[tail]=data[head];
    }
    //将基准值归为
    data[head]=key;
    //此时区间为[left,head-1] head [head+1,right];
    quick_sort(data,left,head-1);
    quick_sort(data,head+1,right);
}

//冒泡排序
void bubble_sort(ElemType *data,int len)
{
    for(int i=0; i<len-1; i++)
    {
        bool flag=true;
        for(int j=0; j<len-1-i; j++)
        {
            if(data[j] > data[j+1])
            {
                int temp=data[j];
                data[j]=data[j+1];
                data[j+1]=temp;
                flag=false;
            }
        }
        if(flag) {
            return;
        }
    }
}

int main() {
    Stable temp,st;
    init_stable1(temp,10);
    init_stable2(st,10);
    //冒泡排序
    memcpy(st.data,temp.data,sizeof(int)*10);
    bubble_sort(st.data,st.size);
    print_stable(st);
    //快速排序（挖坑法）
    memcpy(st.data,temp.data,sizeof(int)*10);
    quick_sort(st.data,0,st.size-1);
    print_stable(st);
    //插入排序
    memcpy(st.data,temp.data,sizeof(int)*10);
    insert_sort(st.data,st.size);
    print_stable(st);
    return 0;
}